package com.lw.leetcode.arr.b;

import java.util.Random;

/**
 * 剑指 Offer II 071. 按权重生成随机数
 * 528. 按权重随机选择
 *
 * @Author liw
 * @Date 2021/8/30 16:06
 * @Version 1.0
 */
class Solution {

    public static void main(String[] args) {
        Random random = new Random();
        for (int i = 0; i < 100; i++) {
            System.out.println(random.nextInt(10));
        }
    }

    private int[] w;
    private Random random;

    public Solution(int[] w) {
        int length = w.length;
        for (int i = 1; i < length; i++) {
            w[i] += w[i - 1];
        }
        this.w = w;
        random = new Random();
    }

    public int pickIndex() {
        int value = random.nextInt(w[w.length - 1]);
        int st = 0;
        int end = w.length - 1;
        while (st < end) {
            int m = st + ((end - st) >> 1);
            if (w[m] > value) {
                end = m;
            } else {
                st = m + 1;
            }
        }
        return st;
    }
}
